package cn.lena.sort;

/**
 * lena
 * 快速排序
 * 2021-03-04
 */
public class ChangeSort {

	/*
	 * t冒泡排序
	 * a ==> 需要排序的数组
	 */
	public int[] bubblingSort(int[] a){
		int tmp,sign;	//sign表示是否发生元素交换
		for(int i=0;i<a.length-1;i++){
			sign=0;
			for(int j=0;j<a.length-i-1;j++){
				if (a[j]>a[j+1]){
					sign=1;
					tmp=a[j];
					a[j]=a[j+1];
					a[j+1]=tmp;
				}
			}
			if (sign==0)
				break;	//无需再排序
		}
		return a;
	}

	/*
	 * t快速排序（不稳定）
	 * a ==> 需要排序的数组
	 * low ==> 比较序列最低位
	 * high ==> 比较序列最高位
	 */
	public int[] fastSort(int[] a,int low,int high){
		// 递归结束
		if (low > high) {
			return a;
		}
		int sign=a[low];	//比较值
		int i=low;
		int j=high;
		while(i != j){		//当i=j时，即当前分区排序完毕，可以进入下一分区的排序
			while(a[j]>=sign && i<j){		//i<j避免越界。若a[j]>=sign则不需要交换
				j--;
			}
			//a[j]<sign，将a[i]与a[j]替换
			if(i<j) {
				a[i]=a[j];
				i++;
			}
			while(a[i]<=sign && i<j){		//i<j避免越界。若a[i]<=sign则不需要交换
				i++;
			}
			//a[i]>sign，将a[i]与a[j]替换
			if(i<j){
				a[j]=a[i];
				j--;
			}
		}
		a[i]=sign;	//将比较值放在i=j位置
		//递归
		fastSort(a,low,i-1);
		fastSort(a,i+1,high);
		return a;
	}

}
